#ifndef I_LIB_IP_I_MORPHOLOGY_H
#define I_LIB_IP_I_MORPHOLOGY_H

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>

#include "../core/i_basic.h"
#include "../core/i_struct.h"

namespace idl{

    typedef std::vector<unsigned int> label_set;
    typedef std::vector<label_set> disjoint_set;
    static void make_set(disjoint_set& ds, unsigned int representive)
    { 
        ds.push_back(std::vector<unsigned int>(1, representive));
    }
    /*Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.*/
    static bool find_set(unsigned int& set_index, const disjoint_set& ds, unsigned int val) 
    {
        if (ds.empty())
        {
            return false;
        }

        bool is_found = false;
        std::vector<label_set>::const_iterator cit_set = ds.begin();
        
        while (cit_set < ds.end())
        {
            std::vector<unsigned int>::const_iterator cit_elem = 
                std::find(cit_set->begin(), cit_set->end(), val);
            if (cit_elem != cit_set->end())
            {
                is_found = true;
                set_index = (unsigned int)(cit_set - ds.begin());//cit_set->front();
                break;
            }
            ++cit_set;
        }
        return is_found;
    }

    /*Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.*/
    static bool find_set(unsigned int& set_index, unsigned int& representive, 
        const disjoint_set& ds, unsigned int val) 
    {
        if (ds.empty())
        {
            return false;
        }
        bool is_found = false;
        std::vector<label_set>::const_iterator cit_set = ds.begin();
        while (cit_set < ds.end())
        {
            std::vector<unsigned int>::const_iterator cit_elem = 
                std::find(cit_set->begin(), cit_set->end(), val);
            if (cit_elem != cit_set->end())
            {
                set_index = (unsigned int)(cit_set - ds.begin());
                is_found = true;
                representive = cit_set->front();
                break;
            }
            ++cit_set;
        }
        return is_found;
    }

    static void union_set(disjoint_set& ds, unsigned int val_0, unsigned int val_1) 
    {
        unsigned int representive_0, representive_1;
        unsigned int set_index_0, set_index_1;

        if (val_0 == val_1)
        {
            return;
        }
        
        bool is_found_0 = find_set(set_index_0, representive_0, ds, val_0);
        bool is_found_1 = find_set(set_index_1, representive_1, ds, val_1);

        if (is_found_0 && is_found_1)
        {
            if (representive_0 == representive_1)
            {
                return;
            }
            else
            {
                if (set_index_1 > set_index_0)
                {
                    std::vector<unsigned int>::const_iterator cit_elem = ds.at(set_index_1).begin();
                    while (cit_elem < ds.at(set_index_1).end())
                    {
                        ds.at(set_index_0).push_back(*cit_elem);
                        ++cit_elem;
                    }
                    ds.at(set_index_1).clear();
                    ds.erase(ds.begin() + set_index_1);
#if 0
                    std::vector<unsigned int>::iterator it_elem = 
                        std::min_element( ds.at(set_index_0).begin(), ds.at(set_index_0).end() );
                    unsigned int tmp = ds.at(set_index_0).front();
                    ds.at(set_index_0).front() = *it_elem;
                    *it_elem =  tmp;                       //swap so the first representive has the smallest value:
#endif
                }
                else
                {
                    std::vector<unsigned int>::const_iterator cit_elem = ds.at(set_index_0).begin();
                    while (cit_elem < ds.at(set_index_0).end())
                    {
                        ds.at(set_index_1).push_back(*cit_elem);
                        ++cit_elem;
                    }
                    ds.at(set_index_0).clear();
                    ds.erase(ds.begin() + set_index_0);
#if 0
                    std::vector<unsigned int>::iterator it_elem = 
                        std::min_element( ds.at(set_index_1).begin(), ds.at(set_index_1).end() );
                    unsigned int tmp = ds.at(set_index_1).front();
                    ds.at(set_index_1).front() = *it_elem;
                    *it_elem =  tmp; //swap so the first representive has the smallest value:
#endif
                }
            }
        }
    }

    //label connected components for birnay image:
    inline int binray_cc8_labeling(const unsigned char* image, unsigned int* labels, 
        const unsigned int width, const unsigned int height)
    {
        const unsigned int imsize = width*height;
        unsigned int neighbor_label[] = {0, 0, 0, 0};
        bool valid[] = {false, false, false};
        
        //i_fill(labels, imsize, (unsigned int)0);
        memset((void*)labels, 0, sizeof(unsigned int)*imsize); /*faster than i_fill*/
        
        disjoint_set ds;
        
        unsigned int global_label = 0;
        const unsigned char* ptr_image = image;
        unsigned int* ptr_label = labels;
        
        //1st pass scan:
        for (int y = 0; y < (int)height; ++y)
        {
            valid[0] = y-1 >= 0 ? true : false;
            for (int x = 0; x < (int)width; ++x)
            {
                if (*ptr_image == 0)
                { 
                    ptr_image++; 
                    ptr_label++; 
                    continue;
                } 
                
                valid[1] = x-1 >= 0 ? true : false;
                valid[2] = x+1 < (int)width ? true : false;
                unsigned int nr_labeled  = 0;
                //maximum label value - every pixel is a single cc.
                unsigned int local_label = imsize+1; 
                neighbor_label[0] = neighbor_label[1] = neighbor_label[2] = neighbor_label[3] = 0;
                
                if (valid[0])
                {
                    //check 1st:
                    if (valid[1])
                    {
                        neighbor_label[0] = *(ptr_label - width - 1);
                        if (neighbor_label[0] > 0)
                        {
                            local_label = i_min(local_label, neighbor_label[0]); 
                            nr_labeled++;
                        }
                    }
                    //check 2nd:
                    neighbor_label[1] = *(ptr_label - width);
                    if (neighbor_label[1] > 0)
                    { 
                        local_label = i_min(local_label, neighbor_label[1]);     
                        nr_labeled++;
                    }
                    //check 3rd:
                    if (valid[2])
                    {
                        neighbor_label[2] = *(ptr_label - width + 1);
                        if (neighbor_label[2] > 0)
                        {
                            local_label = i_min(local_label, neighbor_label[2]); 
                            nr_labeled++;
                        }
                    }
                }
                //check 4th:
                if (valid[1])
                {
                    neighbor_label[3] = *(ptr_label - 1);
                    if (neighbor_label[3] > 0)
                    { 
                        local_label = i_min(local_label, neighbor_label[3]); 
                        nr_labeled++;
                    }
                }
                if (nr_labeled == 0)
                {
                    *ptr_label = ++global_label; 
                    make_set(ds, global_label);
                }
                else if (nr_labeled == 1)
                {
                    *ptr_label = local_label;
                }
                else
                {
                    /*smallest of all neighboring label value*/  
                    /*make a note of the equivalences.*/
                    *ptr_label = local_label;
                    /*pivot must be > 0 given nr_labeled > 1*/
                    unsigned int pivot = *std::max_element(neighbor_label, neighbor_label+4);
                    if (neighbor_label[0] > 0)
                    {  
                        union_set(ds, pivot, neighbor_label[0]);
                    }
                    if (neighbor_label[1] > 0)
                    {  
                        union_set(ds, pivot, neighbor_label[1]);
                    }
                    if (neighbor_label[2] > 0)
                    {  
                        union_set(ds, pivot, neighbor_label[2]);
                    }
                    if (neighbor_label[3] > 0)
                    {  
                        union_set(ds, pivot, neighbor_label[3]);
                    }
                }
                ptr_image++; 
                ptr_label++;
            }
        }
        
        Pair<unsigned int, unsigned int> guard = i_make_pair<unsigned int, unsigned int>(0, 0);
        ptr_label = labels;
        
        //2nd pass merge:
        for (unsigned int i = 0; i<imsize; ++i)
        {
            if (*ptr_label > 0)
            {
                if (*ptr_label == guard.first)
                {
                    *ptr_label = guard.second;
                }
                else
                {
                    unsigned int representive;
                    find_set(representive, ds, *ptr_label); 
                    guard.first = *ptr_label;
                    *ptr_label = guard.second = representive + 1; //0 means background
                }
            } 
            ++ptr_label;
        }
        return (int)ds.size(); //# of cc
    }

} /*namespace idl*/

#endif